{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Vowels of All Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countVowels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有子字符串中的元音"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>word</code> ，返回 <code>word</code> 的所有子字符串中 <strong>元音的总数</strong> ，元音是指 <code>'a'</code>、<code>'e'</code><em>、</em><code>'i'</code><em>、</em><code>'o'</code><em> </em>和 <code>'u'</code><em> 。</em></p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中一个连续（非空）的字符序列。</p>\n",
    "\n",
    "<p><strong>注意：</strong>由于对 <code>word</code> 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"aba\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "所有子字符串是：\"a\"、\"ab\"、\"aba\"、\"b\"、\"ba\" 和 \"a\" 。\n",
    "- \"b\" 中有 0 个元音\n",
    "- \"a\"、\"ab\"、\"ba\" 和 \"a\" 每个都有 1 个元音\n",
    "- \"aba\" 中有 2 个元音\n",
    "因此，元音总数 = 0 + 1 + 1 + 1 + 1 + 2 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"abc\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "所有子字符串是：\"a\"、\"ab\"、\"abc\"、\"b\"、\"bc\" 和 \"c\" 。\n",
    "- \"a\"、\"ab\" 和 \"abc\" 每个都有 1 个元音\n",
    "- \"b\"、\"bc\" 和 \"c\" 每个都有 0 个元音\n",
    "因此，元音总数 = 1 + 1 + 1 + 0 + 0 + 0 = 3 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"ltcd\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\"ltcd\" 的子字符串均不含元音。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"noosabasboosa\"\n",
    "<strong>输出：</strong>237\n",
    "<strong>解释：</strong>所有子字符串中共有 237 个元音。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>word</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [vowels-of-all-substrings](https://leetcode.cn/problems/vowels-of-all-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [vowels-of-all-substrings](https://leetcode.cn/problems/vowels-of-all-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aba\"', '\"abc\"', '\"ltcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(word):\n",
    "            if x in 'aeiou':\n",
    "                ans += (n - i) * (i + 1) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if word[i] in 'aeiou':\n",
    "                res +=  (i + 1) * (n - i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        dct = set(\"aeiou\")\n",
    "        ans = 0\n",
    "        n = len(word)\n",
    "        for i in range(n):\n",
    "            if word[i] in dct:\n",
    "                ans += (i+1)*(n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        ans,n=0,len(word)\n",
    "        for i,ch in enumerate(word):\n",
    "            if ch in \"aeiou\":\n",
    "                ans+=(i+1)*(n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        head = -1\n",
    "        now_yuan = 0\n",
    "        yuan_list = ['a', 'e', 'i', 'o' , 'u']\n",
    "        ret = 0\n",
    "        for i in range(0,len(word)):\n",
    "            if word[i] in yuan_list:\n",
    "                now_yuan = i\n",
    "                ret += (now_yuan+1)*(len(word)-now_yuan)\n",
    "                head = now_yuan\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n=len(word)\n",
    "        vowels={'a','e','i','o','u'}\n",
    "        ans=0\n",
    "        for i,ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans+=(i+1)*(n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        s = 'aioue'\n",
    "        ans = 0\n",
    "        n = len(word)\n",
    "        for i, x in enumerate(word):\n",
    "            if x in s:\n",
    "                ans += (n - i) * (i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        s = {'a','e','i','o','u'}\n",
    "        res = 0\n",
    "        n = len(word)\n",
    "        for i in range(n):\n",
    "            if word[i] in s:\n",
    "                res += (i + 1) * (n - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        res=0\n",
    "        s=\"aeiou\"\n",
    "        n=len(word)\n",
    "        for i in range(len(word)):\n",
    "            x=word[i]\n",
    "            if x in s:\n",
    "                res+=(i+1)*(n-i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        ans = cnt = 0\n",
    "        for i, c in enumerate(word, 1):\n",
    "            if c in \"aeiou\":\n",
    "                cnt += i\n",
    "            ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if word[i] in 'aeiou':\n",
    "                ret += (i + 1) * (n - i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        # 统计每一个原因字符出现位置，然后该字符对所有子字符串的贡献位i+1*(n-i)，然后该字母对答案的共吸纳就是乘法原理\n",
    "        n=len(word)\n",
    "        ans=0\n",
    "        for i,c in enumerate(word):\n",
    "            if c in 'aeiou':\n",
    "                ans+=(i+1)*(n-i)\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if word[i] in \"aeiou\":\n",
    "                res += (i+1) * (n-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        all_yy = ('a','e','i','o','u')\n",
    "        length = len(word)\n",
    "        sum_ = 0\n",
    "        for index,gram in enumerate(word):\n",
    "            if gram in all_yy:\n",
    "                sum_ += (index+1)*(length-index)\n",
    "        return sum_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        s = {'a','e','i','o','u'}\n",
    "        res = 0\n",
    "        n = len(word)\n",
    "        for i in range(len(word)):\n",
    "            if word[i] in s:\n",
    "                res += (i + 1) * (n - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "VOWEL = set('aeiou')\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        base = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(word, 1):\n",
    "            if c in VOWEL:\n",
    "                base += i\n",
    "            ans += base\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        res=0\n",
    "        n=len(word)\n",
    "        for i,c in enumerate(word):\n",
    "            if c in \"aeiou\":\n",
    "                res+=(i+1)*(n-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        lst=['a','e','i','o','u']\n",
    "        result=0\n",
    "        for i in range(0,len(word)):\n",
    "            if word[i] in lst:\n",
    "                result=result+(i+1)*(len(word)-i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        for i, c in enumerate(word):\n",
    "            ans += (c in 'aeiou') * (i+1) * (n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        for i, c in enumerate(word):\n",
    "            if c in 'aeiou':\n",
    "                ans += (i+1) * (n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = {\"a\", \"e\", \"i\", \"o\", \"u\"}\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        ans,n=0,len(word)\n",
    "        for i,ch in enumerate(word):\n",
    "            if ch in \"aeiou\":\n",
    "                ans+=(i+1)*(n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "\n",
    "        #hj a dsfs e sdfs i dsf\n",
    "\n",
    "        #[2,6,8]\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i, s in enumerate(word):\n",
    "            if s in 'aeiou':\n",
    "                left = i - 1 - 0 + 1\n",
    "                right = len(word) - 1 - (i + 1) + 1\n",
    "\n",
    "                res += (left + 1)* (right + 1)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "      n=len(word)\n",
    "      e=['a','e','i','o','u']\n",
    "      ans=0\n",
    "      for i in range(n):\n",
    "         x=word[i]\n",
    "         if x in e:\n",
    "             ans+=(i+1)*(n-i)\n",
    "      return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        y = {'a', 'e', 'i', 'o', 'u'}\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if word[i] in y:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = ['a','e','i','o','u']\n",
    "        ans = 0\n",
    "        for i,ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans += (i+1) * (n-i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = {\"a\", \"e\", \"i\", \"o\", \"u\"}\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        vow = {\"a\", \"e\", \"i\", \"o\", \"u\"}\n",
    "        n = len(word)\n",
    "\n",
    "        res = 0\n",
    "        for i, c in enumerate(word):\n",
    "            if c in vow:\n",
    "                res += (i + 1) * (n - i)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = {\"a\", \"e\", \"i\", \"o\", \"u\"}\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        l=len(word)\n",
    "        i=0\n",
    "        res=0\n",
    "        while i<l:\n",
    "            if word[i] in 'aeiou':\n",
    "                res+=(l-i)*(i+1)\n",
    "            i=i+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "VOWEL = 'aeiou'\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        base = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(word, 1):\n",
    "            if c in VOWEL:\n",
    "                base += i\n",
    "            ans += base\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(word)\n",
    "        for i, c in enumerate(word):\n",
    "            if c in 'aeiou':\n",
    "                ans += (i+1) * (n-i)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = set(['a', 'e', 'i', 'o', 'u'])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if word[i] in vowels:\n",
    "                ans += (n-i) * (i+1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        chars = set('aeiou')\n",
    "        answer = 0\n",
    "        \n",
    "        for i, char in enumerate(word):\n",
    "            if char in chars:\n",
    "                answer += (i + 1) * (n - i)\n",
    "        \n",
    "        return answer\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n=len(word)\n",
    "        ans=0\n",
    "        s={\"a\",\"e\",\"i\",\"o\",\"u\"}\n",
    "        for i in range(n):\n",
    "            if word[i] in s:\n",
    "                ans += (i+1)*(n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        \n",
    "        import sys\n",
    "        sys.set_int_max_str_digits(0)\n",
    "        n = len(word)\n",
    "        # fn = [0 for _ in range(n)]\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            cnt = 1 if word[j] in [\"a\", \"e\", \"i\", \"o\", \"u\"]  else 0\n",
    "            if cnt:\n",
    "                ans += (j+1)*(n-j)\n",
    "            # for i in range(j+1):\n",
    "            #     if j == 0:\n",
    "            #         fn[i] = cnt\n",
    "            #     else:\n",
    "            #         fn[i] = fn[i] + cnt\n",
    "            #     ans += fn[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = set(['a', 'e', 'i', 'o', 'u'])\n",
    "\n",
    "        ans = 0\n",
    "        for i, c in enumerate(word):\n",
    "            if c in vowels:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = {\"a\",\"e\",\"u\",\"i\",\"o\"}\n",
    "        ans = 0\n",
    "        for i,ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans += (i+1)*(n-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countVowels(self, word):\n",
    "        return sum((i + 1) * (len(word) - i) for i, c in enumerate(word) if c in \"aeiou\"  )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(word)\n",
    "        for i in range(n):\n",
    "            if word[i] in ['a','e','i','o','u']:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "VOWEL = set('aeiou')\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = {\"a\", \"e\", \"i\", \"o\", \"u\"}\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        for i,x in enumerate(word):\n",
    "            if x in \"aeiou\":\n",
    "                ans+=(i+1)*(len(word)-i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        vowels = {\"a\", \"e\", \"i\", \"o\", \"u\"}\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(word):\n",
    "            if ch in vowels:\n",
    "                ans += (i + 1) * (n - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        n=len(word)\n",
    "        dic= {\"a\", \"e\", \"i\", \"o\", \"u\"}\n",
    "        res=0\n",
    "        for i,w in enumerate(word):\n",
    "            if w in dic:\n",
    "                res+=(i+1)*(n-i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countVowels(self, word):\n",
    "        return sum((i + 1) * (len(word) - i) for i, c in enumerate(word) if c in \"aeiou\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        seen={'a','e','i','o','u'}\n",
    "        ans=0\n",
    "        N=len(word)\n",
    "        \n",
    "        for i in range(N):\n",
    "            if word[i] in seen:\n",
    "                ans+=(i+1)*(N-i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        res=0\n",
    "        l=len(word)\n",
    "        for i in range(l):\n",
    "            if word[i] in 'aeiou':\n",
    "                res+=(i+1)*(l-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        a = b = s = 0\n",
    "        for i in range(len(word)):\n",
    "            if word[i] in {'a','e','i','o','u'}:\n",
    "                a,b = a+1, b+a+1\n",
    "            else:\n",
    "                a,b = a+1, b\n",
    "            s += b\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        table = ['a','e','i','o','u']\n",
    "        table = set(table)\n",
    "        n = len(word)\n",
    "        res = Counter()\n",
    "        cnt = Counter()\n",
    "        arr = [0] * n\n",
    "        cnt[0] += 1\n",
    "        c = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if word[i] in table:\n",
    "                ans += (i+1)*(n-i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowels(self, word: str) -> int:\n",
    "        # dp[i]  以i位置结尾的元音总数\n",
    "        # dp[i] = \n",
    "        n = len(word)\n",
    "        dp = [0] * (n+1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            dp[i+1] = dp[i] + (word[i] in \"aeiou\") * (i+1)\n",
    "\n",
    "        return sum(dp)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
